package com.lsa.cormen.ch15.samples;

import java.util.Arrays;

import junit.framework.Assert;
import junit.framework.TestCase;

public class KnapsackTest extends TestCase {
    public void testKnapsack1() {
        Integer[] taken = Knapsack.knapsackByDp(165, new int[] { 23, 31, 29,
                44, 53, 38, 63, 85, 89, 82 }, new double[] { 92.0, 57.0, 49.0,
                68.0, 60.0, 43.0, 67.0, 84.0, 87.0, 72.0 }); // knapsack,
                                                             // weights, cost in
                                                             // $
        Assert.assertTrue(Arrays.equals(new Integer[] { 0, 1, 2, 3, 5 }, taken));
    }

    public void testKnapsack2() {
        Integer[] taken = Knapsack.knapsackByDp(26,
                new int[] { 12, 7, 11, 8, 9 }, new double[] { 24.0, 13.0, 23.0,
                        15.0, 16.0 }); // knapsack, weights, cost in $
        Assert.assertTrue(Arrays.equals(new Integer[] { 1, 2, 3 }, taken));
    }

    public void testKnapsack3() {
        Integer[] taken = Knapsack.knapsackByDp(190, new int[] { 56, 59, 80,
                64, 75, 17 },
                new double[] { 50.0, 50.0, 64.0, 46.0, 50.0, 5.0 }); // knapsack,
                                                                     // weights,
                                                                     // cost in
                                                                     // $
        Assert.assertTrue(Arrays.equals(new Integer[] { 0, 1, 4 }, taken));
    }

    public void testKnapsack4() {
        Integer[] taken = Knapsack.knapsackByDp(50, new int[] { 31, 10, 20, 19,
                4, 3, 6 }, new double[] { 70.0, 20.0, 39.0, 37.0, 7.0, 5.0,
                10.0 }); // knapsack, weights, cost in $
        Assert.assertTrue(Arrays.equals(new Integer[] { 0, 3 }, taken));
    }

    public void testKnapsack5() {
        Integer[] taken = Knapsack.knapsackByDp(104, new int[] { 25, 35, 45, 5,
                25, 3, 2, 2 }, new double[] { 350.0, 400.0, 450.0, 20.0, 70.0,
                8.0, 5.0, 5.0 }); // knapsack, weights, cost in $
        Assert.assertTrue(Arrays.equals(new Integer[] { 0, 2, 3, 4, 6, 7 },
                taken));
    }

    public void testKnapsack6() {
        Integer[] taken = Knapsack.knapsackByDp(170, new int[] { 41, 50, 49,
                59, 55, 57, 60 }, new double[] { 442.0, 525.0, 511.0, 593.0,
                546.0, 564.0, 617.0 }); // knapsack, weights, cost in $
        Assert.assertTrue(Arrays.equals(new Integer[] { 1, 3, 6 }, taken));
    }

    public void testKnapsack7() {
        Integer[] taken = Knapsack
                .knapsackByDp(750, new int[] { 70, 73, 77, 80, 82, 87, 90, 94,
                        98, 106, 110, 113, 115, 118, 120 }, new double[] {
                        135.0, 139.0, 149.0, 150.0, 156.0, 163.0, 173.0, 184.0,
                        192.0, 201.0, 210.0, 214.0, 221.0, 229.0, 240.0 }); // knapsack,
                                                                            // weights,
                                                                            // cost
                                                                            // in
                                                                            // $
        Assert.assertTrue(Arrays.equals(new Integer[] { 0, 2, 4, 6, 7, 8, 13,
                14 }, taken));
    }

//    public void testKnapsack8() {
//        Integer[] taken = Knapsack.knapsackByDp(6404180, new int[] { 382745,
//                799601, 909247, 729069, 467902, 44328, 34610, 698150, 823460,
//                903959, 853665, 551830, 610856, 670702, 488960, 951111, 323046,
//                446298, 931161, 31385, 496951, 264724, 224916, 169684 },
//                new double[] { 825594.0, 1677009.0, 1676628.0, 1523970.0,
//                        943972.0, 97426.0, 69666.0, 1296457.0, 1679693.0,
//                        1902996.0, 1844992.0, 1049289.0, 1252836.0, 1319836.0,
//                        953277.0, 2067538.0, 675367.0, 853655.0, 1826027.0,
//                        65731.0, 901489.0, 577243.0, 466257.0, 369261.0 }); // knapsack,
//                                                                            // weights,
//                                                                            // cost
//                                                                            // in
//                                                                            // $
//        Assert.assertTrue(Arrays.equals(new Integer[] { 0, 1, 3, 4, 5, 9, 10,
//                12, 15, 21, 22, 23 }, taken));
//    }

    public void testKnapsack111() {
        Integer[] taken = Knapsack.knapsackByDp(5, new int[] { 4, 2, 3 },
                new double[] { 10, 4, 7 }); // knapsack, weights, cost in $
        Assert.assertTrue(Arrays.equals(new Integer[] { 1, 2 }, taken));
    }

    public void testKnapsack112() {
        Integer[] taken = Knapsack.knapsackByDp(5, new int[] { 4, 2, 3 },
                new double[] { 100, 4, 7 }); // knapsack, weights, cost in $
        Assert.assertTrue(Arrays.equals(new Integer[] { 0 }, taken));
    }

    public void testKnapsack113() {
        Integer[] taken = Knapsack.knapsackByDp(5, new int[] { 2, 1, 3, 5 },
                new double[] { 1, 2, 2, 3 }); // knapsack, weights, cost in $
        Assert.assertTrue(Arrays.equals(new Integer[] { 1, 2 }, taken));
    }
}
